1. Field of the Invention
The present invention is directed to a method, system, and data structure, for finding a ray-object intersection. More particularly, the present invention is directed to a lightweight polyhedrization data structure, using it to find an intersection, and using it to quickly find successive unoccluded or Nth-closest intersections when relatively minor movements of the ray or object occur relative to each other.
2. Description of the Related Art
FIG. 1 shows a ray 50 originating at a virtual camera or viewpoint 52 and intersecting an object 54 at an intersection 56. A screen buffer 58 is also shown. It is a well-known problem in the field of computer graphics to need to find the intersection between a ray and an object. Ray-object intersections are used for various applications such as ray-tracing, painting onto 3-D models, virtual space simulation such as collision detection, and so on.
Finding an intersection between a ray and a simple object such as a sphere, plane, polyhedron, etc. is not difficult. However, it is a nontrivial problem to efficiently find an intersection between a ray and a complex object such as a mesh surface, and in particular it is nontrivial to efficiently find the intersection that is closest to the origin of the ray.
FIG. 2 shows a prior art technique for finding a ray-object intersection. An intersection can be found by first rendering 70 every pixel onto the screen or screen buffer 58.
Then, starting 72 from the object 54, triangles are projected 74 back onto the screen buffer 58, which fills the screen buffer 58 with the frontmost pixels of the object 54 as viewed from the virtual camera 52. The intersection 56 of the ray 50 with the object 54 is determined 76 by reading 78 pixels from the screen buffer 58. The pixel intersecting with the ray 50 tells 80 which face or part of the object 54 is closest to the virtual camera 52. There are several drawbacks to this prior art intersection technique. If the viewpoint or virtual camera 52 changes, or if the object 54 is rotated, translated, modified, etc., then the entire process must be repeated, including recomputing the contents of the buffer 58. Furthermore, the resolution or granularity of the intersection 56 depends on the resolution of the screen buffer 58. It is not possible to definitely determine an intersection with a feature of the object 54 that is more precise than the size of a pixel in the screen buffer 58. Also, the prior art has generally used graphics hardware such as a graphics card to compute depth using a Z buffer. However, such hardware has limited depth precision, such as 16 or 24 bits, which may introduce depth precision artifacts for objects that are close to each other.
The prior art has not been able to obtain the N closest intersections to the ray's origin or an arbitrary Nth-closest intersection. Nor has the prior art observed that this ability could be useful when working with transparent or semi-transparent surfaces.
FIG. 3 shows another prior art technique for finding a ray-object intersection. The technique uses a grid or buffer of object IDs that indicate which faces of object 54 correspond to which pixels. First, a bounding box is computed 100 for the object 54. The bounding box is subdivided 102 where some geometry of the object 54 is encountered. This is repeated until a predetermined stopping point is reached 104. The resulting bounding box tree and voxels (object IDs) are used to determine 106 the intersection 56. This technique also has problems.
One triangle can belong to several voxels, so matching between a small element in the grid and the piece of geometry is not a one-to-one matching. It is also necessary to determine when to stop subdividing the bounding box tree. If the bounding box is subdivided 102 more than necessary, then memory use and performance will be adversely affected. Inadequate subdividing 102 can result in insufficient resolution.
What is needed is a system, method, and data structure for efficiently determining ray-object intersections without disadvantages such as those mentioned above.